package JavaStudy.sort;
//直接插入排序
/*
* 检查第I个数，如果小于左边的数，就对调
* */
public class InsertSort {

    public static int[] sort(int[] arr) {
        if (arr.length >= 2) {
            for (int i = 1; i < arr.length; i++) {
                //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
                int x = arr[i];
                int j = i - 1;
                //在前面有一个或连续多个值比x大的时候,一直循环往前面找,将x插入到这串值前面
                while (j >= 0 && arr[j] > x) {//arr[j]是前面的数，若大于x，表示需要这个数需要后移
                    //当arr[j]比x大的时候,将j向后移一位,正好填到坑中
                    arr[j + 1] = arr[j];
//                    System.out.print(" (左移"+x+") ");
                    j--;
                }
                arr[j + 1] = x;//后移完毕后，将x插入到最前面的空位上

                for (int kk:arr){
                    System.out.print(kk+" ");
                }
                System.out.println("   这是第"+i+"个数,该数为"+arr[i]);
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] a={7,6,3,9,5,4,2,8,1};
        int[] b=sort(a);
    }
}
